1. Field of the Invention
The present invention relates to state machines and in particular to a method of state splitting for increasing device speed.
2. Description of the Related Art
State machines are well known in the art. State machines are sequential logic systems whose output signals are a function of previous and present input signals, in contrast to combinational logic systems whose output signals are a function of present input signals alone. State machines typically include one or more storage elements and occupy a plurality of states which are determined by input signals and the contents of one or more storage elements. A state machine moves sequentially between states, i.e. one state becomes inactive and another state becomes active, in response to the input signals and transition rules established by combinational logic which defines a logic path between the states. A state machine is typically incorporated into a circuit which includes combinational logic and sequential logic circuitry, and frequently serves as a controller for the rest of the circuit.
State machine design typically starts with the translation of a concept into a "paper design," usually in the form of a state diagram which is a pictorial description of the state relationships. FIG. 1 illustrates a state machine 100 which transitions through six states: state 101, state 102, state 103, state 104, state 105, and state 106. Arrows to and from states 101-106 indicate the transitions between states. The input condition that causes a particular state transition is indicated by the first bit written next to each arrow. The second bit written next to each arrow represents the output condition. Equations 1-6 further describe state machine 100. EQU State 101=a(State 101+State 102+State 103+State 104+State 105+State 106)(Eq. 1) EQU State 102=a(State 101+State 106) (Eq. 2) EQU State 103=a(State 102) (Eq. 3) EQU State 104=a(State 103) (Eq. 4) EQU State 105=a(State 104) (Eq. 5) EQU State 106=a(State 105) (Eq. 6)
wherein a indicates the input bit is a logic 1 and a indicates the input bit is a logic 0. Referring to FIG. 1 and Equation 5 for example, state 105 occurs only if a logic 1 as the input bit is provided in state 104. Similarly, referring to FIG. 1 and Equation 1, state 101 occurs if a logic 0 as the input bit is provided in any of states 101-106. The input bits are explained in further detail in reference to FIG. 2. The transitions that produce a particular state are called the fanin transitions of the state. Thus, for example, state 101 has six fanin transitions, whereas state 102 has two fanin transitions.
The actual hardware used to implement state machine 100 consists of flip-flops, referred to as state registers, and gates, referred to as combinational logic. State registers store the current state until the next state is calculated, and the combinational logic performs functions that calculate the next state based on the present state and the present value of the input bits. For example referring to FIGS. 1 and 2, the hardware to implement state machine 100 includes state registers 211 and combinational logic 210.
State registers 211 include flip-flops 201-206, whereas combinational logic 210 includes function generators 212A-212D, 213A, 213B, and 214. In one embodiment, these function generators are implemented using logic gates. For example, function generators 212A-212D in this embodiment are AND gates; function generators 213A and 213B each include an OR gate which provides a signal to an AND gate. The AND gate receives another input signal (signal "a") from a source external to the state machine; and function generator 214 is an OR gate. Note that in Equations 1-6, the "+" indicates an OR function and no symbol indicates an AND function. In another embodiment, the above-referenced function generators are implemented using look-up tables which are well known in the art and therefore not described in detail herein.
The states in state machine 100 are represented by setting certain values in the set of state registers 211 via combinational logic 210. This process is conventionally called state encoding. As shown in FIG. 2, each state is implemented with zero or more function generators and an associated flip-flop. For example, state 101 is implemented with function generators 213A and 214 as well as flip-flop 201. Similarly, state 105 is implemented with function generator 212C and flip-flop 205. Implementing state machine 100 by providing a flip-flop for each state is called "one-hot" encoding. In other words, only one flip-flop of flip-flops 201-206 stores a logic one (all other flip-flops store a logic zero).
One-hot encoding is particularly applicable to state machines implemented with field programmable gate arrays (FPGAs) which have a register-rich architecture and fanin-limited function generators. FPGAs are described in detail in U.S. Reissue Pat. No. Re. 34,363, reissued on Aug. 31, 1993, which is herein incorporated by reference in its entirety. FPGAs include a plurality of configurable logic blocks (CLBs) which are interconnected to one another via an interconnect array. In one embodiment, each CLB includes at least one function generator and at least one flip-flop, hence the register-rich designation. This CLB embodiment is described in detail in U.S. Pat. No. 4,706,216, issued Nov. 10, 1987, which is herein incorporated by reference in its entirety.
Each function generator in a CLB receives a predetermined number of input signals dependent on its FPGA architecture, hence the fanin-limited designation. With one-hot encoding, a state machine having a state with a large number of fanin transitions is implemented by a circuit having at least two sequentially coupled CLBs (i.e. multiple levels of logic). For example referring to FIG. 1, state 101 receives six input signals. Assuming each function generator of a CLB receives a maximum of five input signals, then at least two levels of CLBs are required to implement state 101. Thus, as shown in FIG. 2, state 101 is implemented with sequentially coupled function generators 213A and 214, thereby logically necessitating two CLB levels (one for each function generator). Multiple levels of CLBs significantly reduce the speed of performing a logic function because each level of logic becomes valid only after the previous levels have become valid. Therefore, a need arises for a method of reducing logic levels, thereby reducing the delay of performing a logic function.